A document to be processed in an electronic document processing device such as an electronic copier, an optical character recognition system, or a data compression system, may be comprised of different types of information. These different types of information must be processed in different ways to achieve acceptable copy quality or sufficient data compression, or to enable image manipulation. For example, a document may consist of black and white information such as text or line drawings, continuous tone photographs, and raster or dithered images known as half-tones. When the data collected by scanning such a document undergo processing, storage, or printing, the information representing text or line drawings is usually thresholded to create a binary image, while raster or dithered information is grey-scale thresholded, and continuous tone information is dithered. Consequently, it is necessary to identify each portion of the document containing a particular type of information. This process is termed "segmentation."
An automatic segmentation system has two requirements. First, the system must be fast enough to process documents at high speed. Second, the system must be sufficiently robust to handle documents which have printing that is difficult to distinguish, such as brightly colored text on a dark background or photographs containing large bright areas.
Some automatic segmentation systems consist of a single labeling step. For example, U.S. Pat. No. 4,741,046 discloses a system which measures the variation in the number of foreground pixels constituting foreground pixel regions and the density of those pixels to label segments of a scanned image. Single-step processes can be fast but often lack robustness.
To improve robustness, a two-step labeling system can be used. An example of a conventional two-step automatic segmentation system capable of separating text information from half-tone information is disclosed in the European Patent Application No. 0 202 425. In that system, the scanned image of the document is divided into a matrix of subimages four pixels by four pixels in size. Each of these subimages is initially labeled either as TEXT or as an IMAGE according to the intensity of the pixels within the subimage. Because the labeling of comparatively small subimages is subject to statistical fluctuations, the resulting matrix of labeled subimages frequently includes short strings of TEXT-labeled subimages where IMAGE-labeled subimages are predominant, and vice versa. In the final step of the segmentation process, the relaxation step, a context rule is applied to the matrix, which switches the labels of isolated subimages or short runs of subimages to the predominant label in the surrounding environment.
Similar systems have been disclosed, such as in European Patent Application No. 0 100 811 and French Patent Application No. 2,508,747, but are disadvantageous because the labels used in the initial labeling step and the context rules used in the relaxation step require a large number of criteria, which means increased processing time if the systems are to be robust.
It would be desirable, therefore, to develop an automatic document segmentation system which improves both robustness and speed of processing.